/*
 * @lc app=leetcode.cn id=310 lang=cpp
 *
 * [310] 最小高度树
 *
 * https://leetcode.cn/problems/minimum-height-trees/description/
 *
 * algorithms
 * Medium (43.16%)
 * Likes:    660
 * Dislikes: 0
 * Total Accepted:    49.6K
 * Total Submissions: 114.9K
 * Testcase Example:  '4\n[[1,0],[1,2],[1,3]]'
 *
 * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 *
 * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges
 * 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
 *
 * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为
 * 最小高度树 。
 *
 * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
 * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 4, edges = [[1,0],[1,2],[1,3]]
 * 输出：[1]
 * 解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
 *
 * 示例 2：
 *
 *
 * 输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
 * 输出：[3,4]
 *
 *
 *
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= n <= 2 * 10^4
 * edges.length == n - 1
 * 0 <= ai, bi < n
 * ai != bi
 * 所有 (ai, bi) 互不相同
 * 给定的输入 保证 是一棵树，并且 不会有重复的边
 *
 *
 */

// @lc code=start
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        if (n == 1) {
            return {0};
        }
        // degree存储每个节点的度数，即有几条边与这个节点相连
        vector<int> degree(n);
        // hash邻接表
        map<int, vector<int>> hash;
        // 输出结果
        vector<int> ans;
        // 构造hash邻接表
        for (auto &edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            hash[edge[0]].push_back(edge[1]);
            hash[edge[1]].push_back(edge[0]);
        }
        // 将第一圈度为1的节点入队
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1) {
                q.push(i);
            }
        }
        // 进入bfs，每次将度为1的节点入队，每轮出队，都将出队的节点放入ans中，待输出
        while (!q.empty()) {
            ans.clear();
            int m = q.size();
            while (m--) {
                int t = q.front();
                q.pop();
                ans.push_back(t);
                for (auto &item : hash[t]) {
                    // 将item这一层节点去除之后，剩下所有节点的度都-1，因为整张图少了一圈
                    degree[item]--;
                    if (degree[item] == 1) {
                        q.push(item);
                    }
                }
            }
        }
        return ans;
    }
};

// 枚举bfs，超时
/* class Solution {
public:
    // 存储边
    multimap<int, int> hash;
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        int min_level = INT_MAX;
        vector<int> ans;
        for (auto &item : edges) {
            hash.insert(make_pair(item[0], item[1]));
            hash.insert(make_pair(item[1], item[0]));
        }
        for (int k = 0; k < n; ++k) {
            int level = bfs(hash, n, k);
            if (level <= min_level) {
                if (level == min_level) {
                    ans.push_back(k);
                }
                else {
                    min_level = level;
                    ans = {k};
                }
            }
        }
        return ans;
    }

    int bfs(multimap<int, int> &hash, int n, int k) {
        queue<pair<int, int>> sides;
        vector<bool> visited(n, false);
        visited[k] = true;
        int level = 1;
        auto amount = hash.count(k);
        auto iter = hash.find(k);
        while (amount) {
            sides.push(*iter);
            visited[iter->second] = true;
            ++iter;
            --amount;
        }
        while (!sides.empty()) {
            ++level;
            int n_sides = sides.size();
            while (n_sides--) {
                auto [beginPoint, endPoint] = sides.front();
                sides.pop();
                auto cnt = hash.count(endPoint);
                auto it = hash.find(endPoint);
                while (cnt) {
                    if (!visited[it->second]) {
                        sides.push(*it);
                        visited[it->second] = true;
                    }
                    ++it;
                    --cnt;
                }
            }
        }
        return level;
    }
}; */
// @lc code=end
